package problem.ej3;
import java.io.*;
import java.util.*;
public class Ejercicio3{

	protected int[] solucion;
	protected int[] cortes;
	protected int cantCortes;
	int largo;

	BufferedWriter salida;
	/*
	Constructor de la clase, recive como parametro una cadena con la ruta al archivo de entrada.
	*/
	public Ejercicio3(String archivoEntrada){
		String largo,lineaCortes,linea;

		try{
			FileWriter streamSalida = new FileWriter(archivoEntrada+".out");
			this.salida = new BufferedWriter(streamSalida);

			FileInputStream fstream = new FileInputStream(archivoEntrada);
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));

			while ((linea = br.readLine()) != null){

				largo = linea;
				lineaCortes = br.readLine();
				//si hay cortes
				if(inicializarCaso(lineaCortes,largo)){
					llenarMatriz(this.cortes);
					imprimirSolucion();
				}
				//si no hay cortes
				else	
					this.salida.write("-\n");
				

			}
			this.salida.close();
			streamSalida.close();
		}
		catch(Exception e){ 
			System.out.println(e);
		}

	}
	
	/*
	Inicializa el objeto con los parametros del caso, recibiendo como parámetro la linea de los cortes y la del largo del liston. 
	*/
	private boolean inicializarCaso(String lineaCortes,String largoStr){
		

		String[] cortesStr = lineaCortes.split(" ");
		this.cantCortes = cortesStr.length;

		if(cortesStr[0].length() >0){
			this.cortes = new int[this.cantCortes+2];
			this.solucion = new int[this.cantCortes];


			for(int pos=0;pos<this.cantCortes;pos++){
				this.cortes[pos+1] = Integer.parseInt(cortesStr[pos]);
			}
	
			this.cortes[this.cantCortes+1] = Integer.parseInt(largoStr);
			return true;
		}else
			return false;
	}


	public int llenarMatriz(int[] cortes){
		int n = cortes.length;
		//Matriz de costos
		int[][] costo = new int[n][n];
		//Matriz de soluciones. Sol[i][j] contiene el indice del corte que se debe hacer primero en el segmento(i,j) para
		//alcanzar el resultado optimo
		int[][] sol = new int[n][n];
		int fin,costoParcial;
		

        	//segmentos de longitud 1
	        for(int i = 0; i < n-1 ;i++){
	                costo[i][i+1] = 0;
		}
        	//segmentos de longitud 3 o mayor
	        for(int delta = 2; delta < n ; delta++){
	        	for(int inicio = 0; inicio < n-delta ; inicio++){
	                        fin = inicio+delta;
	                        costo[inicio][fin]  = -1;
	        		for(int i = inicio+1; i < fin ; i++){
	                                costoParcial = cortes[fin]-cortes[inicio] + costo[inicio][i]+costo[i][fin];
					//Si el costo es mejor lo considero
	                                if(costo[inicio][fin] == -1 || costoParcial<costo[inicio][fin]){
	                        		costo[inicio][fin] = costoParcial;
						//Para el segmento de 'inicio' a 'fin' hay que usar el corte 'i' primero luego los mejores cortes
						// de 'inicio' a 'i' y de 'i'a 'fin'
						sol[inicio][fin] = i;
					}
				}
			}
		}

		Stack<int[]> pila = new Stack<int[]>();
		int[] tupla = new int[2];
		int[] tuplaTemp = new int[2];
		int indice;

		tupla[0] = 0;tupla[1] = n-1;
		pila.push(tupla);
		for(int i = 0;i<n-2;i++){
			tupla = pila.pop();
			indice = sol[tupla[0]][tupla[1]];
			this.solucion[i] = cortes[indice];
			tuplaTemp = null;

			if(indice<tupla[1]-1){
				tuplaTemp = new int[2];
				tuplaTemp[0] = indice;
				tuplaTemp[1] = tupla[1];
				pila.push(tuplaTemp);
			}
			if(indice>tupla[0]+1){		
				tuplaTemp = new int[2];
				tuplaTemp[0] = tupla[0];
				tuplaTemp[1] = indice;
				pila.push(tuplaTemp);
			}
			
		}
        	return costo[0][n-1];
	}
	/*
	Imprime la solución en el formato solicitado por la cátedra
	*/
	public void imprimirSolucion(){
		String cadena = "";	
		try{	
			if(this.cantCortes>0)
				cadena = String.valueOf(this.solucion[0]);
			
			for(int i=1; i<this.cantCortes;i++){
				cadena+=' '+String.valueOf(this.solucion[i]);
			}
			this.salida.write(cadena+'\n');
		}
		catch(Exception e){System.out.println("Error al imprimir resultados.");}
	}
}

